package com.ztom.daily.n2022.m5;

/**
 * 乘积小于 K 的子数组
 * <p>
 * https://leetcode-cn.com/problems/subarray-product-less-than-k/
 *
 * @author ZhangTao
 */
public class Day05NumSubarrayProductLessThanK {

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 1) {
            return 0;
        }

        // 滑动窗口
        int l = 0;
        int r = 0;
        // 记录窗口内乘积
        int mul = 1;
        int count = 0;

        while (r < nums.length) {
            mul *= nums[r];
            while (mul >= k) {
                // 过期最左侧元素
                mul /= nums[l];
                l++;
            }

            // 累加窗口内的子数组个数
            count += r - l + 1;
            r++;
        }

        return count;
    }
}
